package com.yin.myproject.lis;

import java.util.Arrays;
import java.util.Random;

/**
 * Created by Eason on 2017/9/14 0014.
 */
public class BserchDemo {

    public static void main(String[] args) {
        int[] ints = {1, 33, 99, 95, 72, 23, 80, 72, 29, 17};
        System.out.println("生成的随机数组为：" + Arrays.toString(ints));
        int[] lis = getLis(ints);
        System.out.println("最长递增子序列为：" + Arrays.toString(lis));
    }

    public static int[] randomArray() {
        Random random = new Random();
        int[] array = new int[10];
        for (int i = 0; i < 10; i++) {
            array[i] = random.nextInt(100);
        }
        return array;
    }

    public static int[] getLis(int[] array) {
        int len = 1;
        int[] arrayCopy = new int[array.length];
        arrayCopy[0] = array[0];
        for (int i = 1; i < array.length; i++) {
            System.out.println("arrayCopy is:" + Arrays.toString(arrayCopy));
            if(array[i]>arrayCopy[len-1]){
                //如果下一个数字比当前数字大 len+1 当前元素入栈
                arrayCopy[len]=array[i];
                len++;
            }else{
                if(i==8){
                    System.out.println();
                }
                //如果下一个数字比当前数字小，二分法查找合适的插入位置
                int left = 0;
                int right = len;
                while (left <= right) {
                    int mid = (left + right) / 2;
                    if (arrayCopy[mid] < array[i]) {
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
                arrayCopy[left]=array[i];
                if (left >= len) {
                    len++;
                }
            }
        }
        int lis[] = new int[arrayCopy.length];
//        for (int i = 1; i < arrayCopy.length; i++) {
//            int j = 0;
//            while (array[j] > arrayCopy[i - 1] && array[j] < arrayCopy[i]) {
//                System.out.println("第" + i + "个元素为：" + array[j]);
//                j++;
//                lis[i] = array[j];
//            }
//        }
        return lis;
    }
}
